package com.wk.data.tree;
/**
 *	二叉搜索树又叫排序二叉树
 *	左子节点小于根节点，右子节点大于根节点
 * @author Administrator
 *
 */
public class BST {
	public TreeNode root;
	
	/**
	 * 	查找值
	 * @param key
	 * @return
	 */
	public TreeNode get(int key) {
		TreeNode current = root;
		while (current!=null && current.value!=key) {
			if(current.value>key) {
				current = current.left;
			}
			if(current.value<key) {
				current = current.right;
			}
		}
		return current;
	}
	/**
	 * 	插入值
	 * @param key
	 */
	public void insert(int key) {
		if(root == null) {
			root = new TreeNode(key);
			return;
		}
		TreeNode parent = null;
		TreeNode current = root;
		while (true) {
			parent = current;
			if(key < parent.value) {
				current = parent.left;
				if(current == null) {
					parent.left = new TreeNode(key);
					return;
				}
			}else if(key > parent.value) {
				current = parent.right;
				if(current == null) {
					parent.right = new TreeNode(key);
					return;
				}
			}else {
				return;//BST不允许节点有相同值
			}
			
		}
	}
	
	public boolean delete(int key) {
		// 先搜索treeNode
		
		// 在删除treeNode
		
		return true;
	}
}
